#include <algorithm>
#include <vector>
#include <list>

#include "cover.h"

using std::vector;
using std::list;
using std::max_element;
using std::swap;

/**
 * private comparison predicate object used by the priority_queue in 
 * greedy_vc2. Compares integers by treating them as row indices and 
 * comparing the corresponding rowsums. Needs an array of row sums 
 * to compare with, hence the lack of a default constructor.
 */
class rowsum_cmp_t
{
    private:
	/**
	 * pointer to array of rowsums
	 */
	int * _rowsums;

    public:
	// no default constructor b/c argument is mandatory

	/**
	 * @param   rowsums	a rowsums matrix
	 */
	rowsum_cmp_t (int * rowsums) : _rowsums(rowsums) {}

	/**
	 * Compares by rowsums using arguments as indices. Does not check
	 * index bounds, so assumes input indices are valid.
	 * @param   i	index of first row
	 * @param   j	index of second row
	 * @return  true if rowsum of row i is less than rowsum of row j
	 */
	bool operator()(int i, int j) {
	    return _rowsums[i] < _rowsums[j];
	}
};

/**
 * Improved greedy algorithm based on Set Cover
 * Modifies: matrix, cover, solutions
 *
 * @param   matrix	the 0,1 matrix as vector of vectors of int
 * @param   ncols   	number of data columns representing lines,
 *		    	not number of characters
 * @param   nrows   	number of rows
 * @param   cover   	int array of length ncols
 * @param   solutions	a storage container for solution row indices
 */
void greedy_isc (
	vector<vector<int> > &matrix,
	size_t nrows,
	size_t ncols,
	int *cover,
	list<int> &solutions
	)
{
    /**
     * Algorithm description
     *
     * while not finished covering
     *. count the number of 1's in each column
     *. find the first uncovered column with smallest column sum
     *. choose the first row in that column with greatest rowsum
     *	    - cover the matrix with that row
     *
     * The point of this algorithm is to improve the set cover algorithm
     * by giving priority to vertices which must be chosen because they
     * happen to be the only one that sees certain segments.
     */

    int *colsums = new int[ncols];
    int *rowsums = new int[nrows];

    /* initialize row and column sums */
    initialize_row_column_sums (matrix, rowsums, colsums);

    while ( !finished(cover, ncols) ) {
	// find min col that has NOT been covered yet
	// !finished() guarantees one exists
	int colj, mincolj;
	colj = mincolj = 0;
	while (colj < ncols) {
	    // if mincolj is covered, advance it
	    if ((cover[mincolj] == 1) || 
		(cover[colj] != 1) && (colsums[mincolj] > colsums[colj])
		)
	    {
		mincolj = colj;
	    }
	    ++colj;
	}
	// POST: mincolj == index of minimum uncovered column sum

	// "less than" predicate object
	rowsum_cmp_t rowsum_less(rowsums);

	/* temporary storage for rows to cover */
	list<int> row_indices;

	// save all indices of rows i with a 1 in mincol 
	// if we cover matrix here, all other 1's in the column are lost
	// so we save all the row indices first
	int endrow = matrix.size();
	for (int i=0; i<endrow; i++) {
	    if ( matrix.at(i).at(mincolj) == 1 ) { 
		row_indices.push_back(i);
	    }
	}

	list<int>::iterator firstitr = row_indices.begin();
	list<int>::iterator lastitr = row_indices.end();

	// find the row index with largest rowsum
	list<int>::iterator swapitr
	    = max_element(firstitr, lastitr, rowsum_less);
	int rowi = *swapitr;
	vector<int> &row = matrix.at(rowi);

	// add it to solution set
	solutions.push_back(rowi);
	cover_with_row (matrix, rowi, cover, rowsums, colsums);
    }

    /* clean up duty -- free up memory */
    delete[] colsums;
    delete[] rowsums;
}

